The present invention relates to log structured arrays for storage subsystems, and more particularly to increasing concurrency during staging and destaging in a log structured array.
In storage subsystems, a redundant array of inexpensive disks, RAID, is one solution to I/O (input/output) bottleneck problems. RAID typically increases disk bandwidth through parallelism for accessing data and provides high data availability through redundancy. One problem associated with some levels of RAID is the write penalty; a write operation actually requires two disk reads (of old data and parity) and two disk writes (of updated data and the newly calculated parity). Log Structured Array (LSA) writes all customer data to disk sequentially in a log-like structure and enables RAID to support data compression. The amount of compression achieved is dependent on the actual data values. After a piece of data is modified, it may not compress to the same number of bytes and thus will not fit into the space originally allocated to it. This problem is encountered in any storage system that assigns a piece of data to a disk fixed location; LSA avoids this problem, since updated data is written to end of the log structure.
Through LSA, a logical track, LT, which is the typical unit accessed by I/O programs, is allowed to be updated to a different location on disk. Since the physical address of a logical track changes over time, a directory, called LSA directory, is necessary to keep track of the current LT""s physical address on the array. Each directory entry also records the logical track""s current length, as this may vary with compression.
The log structured array consists of N+P+S physical disk drives, where N is the number of HDDs"" (hard disk drive) worth of physical space available for customer data, P is the number of HDDs"" worth of physical space for parity data, and S is the number of HDDs"" worth of physical space for spare drives. Each HDD is divided into large consecutive areas called segment columns. Typically, a segment column is as large as a logical cylinder. Corresponding segment columns from the N+P+S HDDs constitute a segment. The array has as many segments as there are segment columns on a HDD disk in the array. An example of the layout for such a system is shown in FIG. 1. In a RAID-5 configuration, one of the segment columns of a segment contains the parity of the remaining data segment columns of the segment.
Referring to FIG. 1, the storage for the partition 52 is arranged as segments 56, where each segment has N data segment columns 58 and one parity segment column 59. The logical tracks 60 are stored within segment columns. A segment directory 62 contains information on each of the logical tracks in the segment which is used during garbage collection and recovery procedures. The segment directory 62 is stored in a small number of sectors out of a segment""s total disk space. As shown, the entire segment directory resides in one same segment column in each of the segments. Alternatively, the segment directory can be spread among the devices. In a RAID-5 system, parity is distributed among the devices as shown.
A segment column is defined as an arbitrary number of contiguous physical tracks as described above. Typically it is desirable to define a segment column to be the same size as a logical cylinder. The collection of disk recording areas comprising corresponding segment columns from each of the HDDs forms what is called a segment.
LSA segments are categorized as one of the following types: free, which refers to a segment that contains no valid data; open, which refers to a segment that is available to hold LTs being destaged; closed, which refers to a segment containing some valid data, but to which no destaged data can be further assigned; and being garbage collected, GC, which refers to a closed segment that is currently being garbage collected, as discussed hereinbelow. A closed segment consists of xe2x80x98livexe2x80x99 LTs and xe2x80x98holesxe2x80x99. The former are LTs that were assigned to the segment during the segment""s open phase and still reside in the segment. The latter is space vacated by LTs that were assigned to the segment but have subsequently been updated and assigned to different open segments. A closed segment""s occupancy is the sum of the lengths of the segment""s live LT.
A destage operation allows the LTs in a logical cylinder to be destaged together from a cache within the storage subsystem to the storage device to enhance the seek affinity of sequential accesses. A logical cylinder is typically called a neighborhood, and a group of logical tracks in a logical cylinder destaged together is called a neighborhood in destage (NID) or neighborhood destage request. Destaging a neighborhood essentially involves the following steps:
1. The neighborhood in destage is assigned to an open segment.
2. An open segment remains available to accept other neighborhoods in destage until it is deemed full enough to close in accordance with a desired algorithm.
3. The data and parity of the segment is written to disk before the segment is considered closed.
4. Each LT in the open segment has an entry in the segment directory that describe the LT""s location in the segment. The segment directory is written on disk, as part of the segment.
An LT in a closed segment may be updated and destaged again, at which time it is assigned to another open segment. This causes the previous copy of the LT to become obsolete, thus forming a xe2x80x98holexe2x80x99 in the closed segment. Garbage collection (GC) is the process of reclaiming xe2x80x98holesxe2x80x99 in closed segments. GC is started when the number of free segments falls below a certain threshold.
The process of garbage collecting a segment involves reading the segment""s directory from disk, then scanning each segment directory entry and comparing the LT""s address as indicated by the segment directory entry with the address as indicated by the LSA directory entry. If the two entries match, then the LT still resides in the segment and is considered xe2x80x98livexe2x80x99. All the live LTs are then read from disk into memory and sorted by neighborhood. These NIDs then proceed to be destaged in the same manner as described above. These NIDs are assigned to open segments; when such open segments close successfully, the NIDs are garbage collected, thus decreasing the occupancy of the segments in which the NIDs previously resided. When a segment""s occupancy declines to zero, either as a result of garbage collection or as a result of movement of tracks from normal destage activity, the segment becomes free.
The LSA directory keeps track of LTs"" length and physical address in the disk array in terms of segment number, segment column number, and offset within the segment column. An LT""s LSA directory entry is accessed whenever the LT is involved in any one of the three major processes: staging of data from disk, destaging of data to disk, and garbage collection. When an LT is staged, its LSA directory entry is read to determine the LT""s physical location in the array. When an LT is destaged, its physical address changes and its LSA directory entry must be updated to indicate the new location. Likewise, when the LT is garbage collected, the track changes physical location, and the LSA directory entry must be updated.
Conflicts in access of the LSA directory entry arise when a logical track is involved in the following combination of concurrent operations: destage and garbage collection, or stage and garbage collection. Design of the interface between the disk control unit""s caching component and its array component prohibits concurrent stage and destage of the same LT. Similarly, an LT cannot be destaged a second time before a first destage operation completes; and an LT cannot be staged a second time before a first stage operation completes. In the other cases, the LSA directory entry locking mechanism provided by the LSA subcomponent must handle the concurrent accesses.
One straightforward approach for handling concurrent accesses is to simply serialize the operations. That is, the destage operation is not allowed to begin if the LT is in a segment currently being garbage collected; a segment is not allowed to begin garbage collection if it contains an LT that is being destaged; a segment is not allowed to be garbage collected if it contains an LT currently being staged; and an LT is not allowed to be staged if it resides in a segment that is undergoing garbage collection. Unfortunately, such a solution sacrifices efficiency and performance. If an LT is currently being garbage collected when a destage request for the LT arrives, it is inefficient to force the destage operation to wait while the garbage collection process moves the LT to a different location, as the destage operation will accomplish the same result. It also degrades the destage performance a great deal, since the destage request, normally at higher priority than garbage collection, has to wait for the relatively time-consuming garbage collection process to finish before the destage can proceed. Similarly, if an LT is currently being garbage collected when a stage request for the LT arrives, then performance of the stage operation would be unacceptably slow if it were forced to wait for the garbage collection process to complete.
Accordingly, a need exists for increased concurrency during staging and destaging in a log structured array. The present invention addresses such a need.
The present invention provides aspects for increasing concurrency during staging and destaging of a log structured array (LSA). In an exemplary method aspect, the method includes determining a process type making a request for access to a locking mechanism associated with an LSA directory entry for a logical track, and determining a lock status for the locking mechanism. Access to the locking mechanism is then provided according to the determined process type and lock status. Further, a destaging process is allowed to obtain an available locking mechanism in a read-write mode, a staging process is allowed to obtain an available locking mechanism in a read-only mode, and a garbage collection process is allowed to obtain an available locking mechanism initially in a read-only mode and subsequently in a read-write mode, wherein increased concurrency results during the staging and destaging processes.
Through the present invention, conflicting processes have a greater degree of concurrency than that under serialization of processes. Additionally, utilization of a specialized shared lock in each LT""s LSA directory entry efficiently directs which process type(s) operate on an LT. These and other advantages of the aspects of the present invention will be more fully understood in conjunction with the following detailed description and accompanying drawings.